Search for: All records

ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems. Some of our proofs are based on the method of graph Lagrangians, while the other proofs use flag algebras. Using these results, we prove several new upper bounds on the Ramsey‐Turán density of cliques. Other applications of our results are in a recent paper of Balogh, Chen, McCourt, and Murley. 

Abstract Theq-colour Ramsey number of ak-uniform hypergraphHis the minimum integerNsuch that anyq-colouring of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofH. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximise the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed$$k \ge 3$$and$$q \ge 2$$we prove that the largest possibleq-colour Ramsey number of ak-uniform hypergraph withmedges is at most$$\mathrm{tw}_k(O(\sqrt{m})),$$where tw denotes the tower function. We also present a construction showing that this bound is tight for$$q \ge 4$$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for$$k \geq 4$$and the lower bound for$$k=3$$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs. 

Abstract Theq-color Ramsey number of ak-uniform hypergraphG,  denotedr(G; q), is the minimum integerNsuch that any coloring of the edges of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofG. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behavior ofr(G; q) for fixedGandqtending to infinity. In this paper, we study this problem for 3-uniform hypergraphs and determine the tower height ofr(G; q) as a function ofq. More precisely, given a hypergraphG, we determine whenr(G; q) behaves polynomially, exponentially or double exponentially inq. This answers a question of Axenovich, Gyárfás, Liu and Mubayi.